home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / cool / ge_cool.lha / GE_COOL2.1 / src / Hash_Table / TODO < prev   
Encoding:
Text File  |  1992-04-14  |  4.3 KB  |  119 lines
  1.  
  2. Make the (base) ~Hash_Table() destructor method inline.
  3.  
  4. Get rid of the Hash_Table<Tkey,Tval>::Hash_Table<Tkey,Tval> () constructor
  5. and give the constructor that takes a size a default argument:
  6. Hash_Table<Tkey,Tval>::Hash_Table<Tkey,Tval> (int n=1) : (n) {
  7. Do the same for the base Hash_Table class.
  8.  
  9. Move the "traversed" flag in the current position out of Hash_Table, and
  10. only support it in the Set class.
  11.  
  12. Use the following for setting current position:
  13. #define make_current_position(hash, index) ((hash << 8) | index)
  14. this->current_position.data = make_current_position(hash, index);
  15. This helps out compilers that don't optimize well (-g option)
  16. and will be faster, if the "traversed" flag is left in.
  17.  
  18. The resize method can be improved by using the overloaded operator new
  19. in cfront 2.0 to only construct the new buckets, avoid calling the
  20. destructor for the old buckets, and avoid operator= by using memcpy (see
  21. Vector<Type>::resize)
  22.  
  23. Don't try saving the current position in the remove method.  Since it
  24. doesn't always work, it should never be done.
  25.  
  26. Re-write Boolean Hash_Table<Tkey,Tval>::remove (const Tkey& key);
  27. to do a find(key) followed by remove();
  28. (this reduces the amount of code generated for each hash table)
  29.  
  30. Operator= shouldn't make the sizes of the two hash tables the same,
  31. it should just copy the contents.  The current algorithm should be
  32. an optimization for the case where the two sizes are already equal,
  33. or less than.
  34.  
  35. Operator== shouldn't depend on the two hash table's having the same
  36. number of buckets.  It should first check for the number of entries
  37. being the same (which it does), then for each element in the first hash
  38. table, do a find on the second, and compare the values.  The current
  39. algorithm should be used as an optimization for the case where the two
  40. hash tables have the same number of buckets.
  41. DONE
  42.  
  43. find, put, get and remove all have the following inner-loop code:
  44.   long prime = hash_primes[this->current_bucket]; // Prime number of buckets
  45.   unsigned long hash = ((*this->h_function)(key)) % prime; // Get hash value
  46.   int index = this->items_in_buckets[hash];
  47.   for (int i = 0; i < index; i++)        // For each item
  48.     if ((*this->compare_keys)(key,this->table[hash].data[i].key) == TRUE)
  49.       //DO SOMETHING
  50.  
  51. Get rid of the function call in the inner loop by making compare_keys
  52. default to NULL, and moving the default code to a general purpose find
  53. method.  Do the same for default_hash.
  54. The above code can be replaced with:
  55.  
  56.   unsigned long hash;
  57.   int i = this->internal_find(key, &hash);
  58.   if (i < 0) DO_SOMETHING
  59.   else DO_SOMETHING_ELSE
  60.  
  61. // Returns bucket index, or -1 if not found
  62. // If hash_return is non-null, return the hash value
  63. // If hash_return is null, this function returns the hash value
  64. // (this feature is used by the resize method)
  65.  
  66. long Hash_Table<Tkey, Tval>::internal_find(Tkey key, long* hash_return) {
  67.   long prime = hash_primes[this->current_bucket]; // Prime number of buckets
  68.   long hash;
  69.   //
  70.   // Get the hash value
  71.   //
  72.   if (this->h_function != NULL)
  73.     hash = ((*this->h_function)(key)) % prime;
  74.   else {
  75. #if ISSAME(Tkey, charP) || ISSAME(Tkey, String)
  76.     hash = sxhash(key) % prime;
  77. #else
  78.     if (sizeof (key) <= 4)
  79.       hash = (((unsigned long) key) >> 3) % prime;
  80.     else
  81.       hash = sxhash((char*) &key) % prime;
  82. #endif
  83.   }
  84.   if (hash_return == NULL)
  85.     return hash;
  86.   else
  87.     hash_return = hash;
  88.   //
  89.   // Find the bucket entry
  90.   //
  91.   int index = this->items_in_buckets[hash];
  92.   Tkey##_##Tval##_hash_pair bucket[BUCKET_SIZE] = this->table[hash].data;
  93.   if (this->compare_keys == NULL) {    // DEFAULT COMPARE FUNCTION
  94. #if ISSAME(T1, charP)
  95.  #ifndef C_STRINGH
  96.    extern int strcmp (const char*, const char*);
  97.  #endif
  98.     for (int i = 0; i < index; i++)        // For each item
  99.       if (!strcmp(key,bucket[i].key))
  100.         return i;
  101. #else
  102.     for (int i = 0; i < index; i++)        // For each item
  103.       if (key == bucket[i].key)
  104.         return i;
  105. #endif
  106.  
  107.   } else {                // VARIABLE COMPARE FUNCTION
  108.     for (int i = 0; i < index; i++)        // For each item
  109.       if ((*this->compare_keys)(key, bucket[i].key))
  110.         return i;
  111.   }
  112.   return -1;
  113. }
  114.  
  115. This method replaces default_hash and Default_Hash_Compare.  In
  116. addition, it eliminates several function calls in all the lookup
  117. methods, and reduces code duplication (i.e. reduces the amount of code
  118. generated for each hash table)
  119.